package problems.practice;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 剑指 Offer II 091. 粉刷房子
 * <p>https://leetcode.cn/problems/JEj789/</p>
 *
 * @author habitplus
 * @since 12:57, 2022/10/5
 */
public class Office_2_T091 {

    public int minCost(int[][] costs) {
        if (costs == null || costs.length < 1 || costs[0].length != 3) return 0;

        int n = costs.length;
        // 从左到右粉刷房子，
        // r 表示第 i 个房子涂红色的最小花费；
        // b 表示第 i 个房子涂蓝色的最小花费；
        // g 表示第 i 个房子涂绿色的最小花费；
        int r = costs[0][0], b = costs[0][1], g = costs[0][2];
        int tmpR, tmpB, tmpG;

        for (int i = 1; i < n; ++i) {
            // 涂红色
            tmpR = costs[i][0] + Math.min(b, g);
            // 涂蓝色
            tmpB = costs[i][1] + Math.min(r, g);
            // 涂绿色
            tmpG = costs[i][2] + Math.min(r, b);

            r = tmpR;
            b = tmpB;
            g = tmpG;
        }

        return Math.min(r, Math.min(g, b));
    }



    // Time Exceed
    public int minCost1(int[][] costs) {
        // bfs
        if (costs == null || costs.length < 1 || costs[0].length != 3) return 0;

        int n = costs.length;
        int k = 0;
        int ret = Integer.MAX_VALUE;
        Queue<Node> que = new LinkedList<>();
        Node node;

        que.offer(new Node(-1, -1, 0));

        while (!que.isEmpty() && k < n) {

            for (int i = que.size(); i > 0; --i) {
                node = que.poll();

                if (node.no == n - 1) {
                    ret = Math.min(ret, node.cost);
                    continue;
                }

                for (int j = 0; j < 3; ++j) {
                    if (j != node.color) {
                        // 当前房子可以粉刷的颜色
                        que.add(new Node(k, j, costs[k][j] + node.cost));
                    }
                }
            }
            k++;
        }

        return ret;

    }

    class Node {
        // 粉刷完前 no 个房子的花费
        int cost;
        // 房子编号
        int no;
        // 粉刷的颜色编号
        // 0：红；1：蓝；2：绿
        int color;

        public Node(int no, int color, int cost) {
            this.no = no;
            this.color = color;
            this.cost = cost;
        }
    }
}
